home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Collection of Tools & Utilities
/
Collection of Tools and Utilities.iso
/
graphic
/
jpegsrc4.zip
/
JWRGIF.C
< prev
next >
Wrap
C/C++ Source or Header
|
1992-07-26
|
15KB
|
487 lines
/*
* jwrgif.c
*
* Copyright (C) 1991, 1992, Thomas G. Lane.
* This file is part of the Independent JPEG Group's software.
* For conditions of distribution and use, see the accompanying README file.
*
* This file contains routines to write output images in GIF format.
*
* These routines may need modification for non-Unix environments or
* specialized applications. As they stand, they assume output to
* an ordinary stdio stream.
*
* These routines are invoked via the methods put_pixel_rows, put_color_map,
* and output_init/term.
*/
/*
* This code is loosely based on ppmtogif from the PBMPLUS distribution
* of Feb. 1991. That file contains the following copyright notice:
* Based on GIFENCODE by David Rowley <mgardi@watdscu.waterloo.edu>.
* Lempel-Ziv compression based on "compress" by Spencer W. Thomas et al.
* Copyright (C) 1989 by Jef Poskanzer.
* Permission to use, copy, modify, and distribute this software and its
* documentation for any purpose and without fee is hereby granted, provided
* that the above copyright notice appear in all copies and that both that
* copyright notice and this permission notice appear in supporting
* documentation. This software is provided "as is" without express or
* implied warranty.
*
* We are also required to state that
* "The Graphics Interchange Format(c) is the Copyright property of
* CompuServe Incorporated. GIF(sm) is a Service Mark property of
* CompuServe Incorporated."
*/
#include "jinclude.h"
#ifdef GIF_SUPPORTED
static decompress_info_ptr dcinfo; /* to avoid passing to all functions */
#define MAX_LZW_BITS 12 /* maximum LZW code size (4096 symbols) */
typedef INT16 code_int; /* must hold -1 .. 2**MAX_LZW_BITS */
#define LZW_TABLE_SIZE ((code_int) 1 << MAX_LZW_BITS)
#define HSIZE 5003 /* hash table size for 80% occupancy */
typedef int hash_int; /* must hold -2*HSIZE..2*HSIZE */
static int n_bits; /* current number of bits/code */
static code_int maxcode; /* maximum code, given n_bits */
#define MAXCODE(n_bits) (((code_int) 1 << (n_bits)) - 1)
static int init_bits; /* initial n_bits ... restored after clear */
static code_int ClearCode; /* clear code (doesn't change) */
static code_int EOFCode; /* EOF code (ditto) */
static code_int free_code; /* first not-yet-used symbol code */
/*
* The LZW hash table consists of three parallel arrays:
* hash_code[i] code of symbol in slot i, or 0 if empty slot
* hash_prefix[i] symbol's prefix code; undefined if empty slot
* hash_suffix[i] symbol's suffix character; undefined if empty slot
* where slot values (i) range from 0 to HSIZE-1.
*
* Algorithm: use open addressing double hashing (no chaining) on the
* prefix code / suffix character combination. We do a variant of Knuth's
* algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
* secondary probe.
*
* The hash tables are allocated from FAR heap space since they would use up
* rather a lot of the near data space in a PC.
*/
static code_int FAR *hash_code; /* => hash table of symbol codes */
static code_int FAR *hash_prefix; /* => hash table of prefix symbols */
static UINT8 FAR *hash_suffix; /* => hash table of suffix bytes */
/*
* Routines to package compressed data bytes into GIF data blocks.
* A data block consists of a count byte (1..255) and that many data bytes.
*/
static int bytesinpkt; /* # of bytes in current packet */
static char packetbuf[256]; /* workspace for accumulating packet */
LOCAL void
flush_packet (void)
/* flush any accumulated data */
{
if (bytesinpkt > 0) { /* never write zero-length packet */
packetbuf[0] = (char) bytesinpkt++;
if (JFWRITE(dcinfo->output_file, packetbuf, bytesinpkt)
!= (size_t) bytesinpkt)
ERREXIT(dcinfo->emethods, "Output file write error");
bytesinpkt = 0;
}
}
/* Add a character to current packet; flush to disk if necessary */
#define CHAR_OUT(c) \
{ packetbuf[++bytesinpkt] = (char) (c); \
if (bytesinpkt >= 255) \
flush_packet(); \
}
/* Routine to convert variable-width codes into a byte stream */
static INT32 cur_accum; /* holds bits not yet output */
static int cur_bits; /* # of bits in cur_accum */
LOCAL void
output (code_int code)
/* Emit a code of n_bits bits */
/* Uses cur_accum and cur_bits to reblock into 8-bit bytes */
{
cur_accum |= ((INT32) code) << cur_bits;
cur_bits += n_bits;
while (cur_bits >= 8) {
CHAR_OUT(cur_accum & 0xFF);
cur_accum >>= 8;
cur_bits -= 8;
}
/*
* If the next entry is going to be too big for the code size,
* then increase it, if possible. We do this here to ensure
* that it's done in sync with the decoder's codesize increases.
*/
if (free_code > maxcode) {
n_bits++;
if (n_bits == MAX_LZW_BITS)
maxcode = LZW_TABLE_SIZE; /* free_code will never exceed this */
else
maxcode = MAXCODE(n_bits);
}
}
/* The LZW algorithm proper */
static code_int waiting_code; /* symbol not yet output; may be extendable */
static boolean first_byte; /* if TRUE, waiting_code is not valid */
LOCAL void
clear_hash (void)
/* Fill the hash table with empty entries */
{
/* It's sufficient to zero hash_code[] */
jzero_far((void FAR *) hash_code, HSIZE * SIZEOF(code_int));
}
LOCAL void
clear_block (void)
/* Reset compressor and issue a Clear code */
{
clear_hash(); /* delete all the symbols */
free_code = ClearCode + 2;
output(ClearCode); /* inform decoder */
n_bits = init_bits; /* reset code size */
maxcode = MAXCODE(n_bits);
}
LOCAL void
compress_init (int i_bits)
/* Initialize LZW compressor */
{
/* init all the static variables */
n_bits = init_bits = i_bits;
maxcode = MAXCODE(n_bits);
ClearCode = ((code_int) 1 << (init_bits - 1));
EOFCode = ClearCode + 1;
free_code = ClearCode + 2;
first_byte = TRUE; /* no waiting symbol yet */
/* init output buffering vars */
bytesinpkt = 0;
cur_accum = 0;
cur_bits = 0;
/* clear hash table */
clear_hash();
/* GIF specifies an initial Clear code */
output(ClearCode);
}
LOCAL void
compress_byte (int c)
/* Accept and compress one 8-bit byte */
{
register hash_int i;
register hash_int disp;
if (first_byte) { /* need to initialize waiting_code */
waiting_code = c;
first_byte = FALSE;
return;
}
/* Probe hash table to see if a symbol exists for
* waiting_code followed by c.
* If so, replace waiting_code by that symbol and return.
*/
i = ((hash_int) c << (MAX_LZW_BITS-8)) + waiting_code;
/* i is less than twice 2**MAX_LZW_BITS, therefore less than twice HSIZE */
if (i >= HSIZE)
i -= HSIZE;
if (hash_code[i] != 0) { /* is first probed slot empty? */
if (hash_prefix[i] == waiting_code && hash_suffix[i] == (UINT8) c) {
waiting_code = hash_code[i];
return;
}
if (i == 0) /* secondary hash (after G. Knott) */
disp = 1;
else
disp = HSIZE - i;
while (1) {
i -= disp;
if (i < 0)
i += HSIZE;
if (hash_code[i] == 0)
break; /* hit empty slot */
if (hash_prefix[i] == waiting_code && hash_suffix[i] == (UINT8) c) {
waiting_code = hash_code[i];
return;
}
}
}
/* here when hashtable[i] is an empty slot; desired symbol not in table */
output(waiting_code);
if (free_code < LZW_TABLE_SIZE) {
hash_code[i] = free_code++; /* add symbol to hashtable */
hash_prefix[i] = waiting_code;
hash_suffix[i] = (UINT8) c;
} else
clear_block();
waiting_code = c;
}
LOCAL void
compress_term (void)
/* Clean up at end */
{
/* Flush out the buffered code */
if (! first_byte)
output(waiting_code);
/* Send an EOF code */
output(EOFCode);
/* Flush the bit-packing buffer */
if (cur_bits > 0) {
CHAR_OUT(cur_accum & 0xFF);
}
/* Flush the packet buffer */
flush_packet();
}
/* GIF header construction */
LOCAL v